//
// Created by NASA on 2024/6/29.
//
/*二分查找变形
 *查找第一个/ 最后一个值等于给定值的元素
 * OJ: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *查找第一个/ 最后一个值大于等于给定值的元素
 *
 * 讲解:  http://t.csdnimg.cn/uspHf
 * https://www.cnblogs.com/sunshuyi/p/12681088.html
 * */

#include <iostream>
#include <vector>

using namespace std;

int searchEqual(vector<int> l, int x)
{
    int left = 0, right = l.size() - 1, mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (x < l[mid])
        {
            right = mid - 1;
        } else if (x > l[mid])
        {
            left = mid + 1;
        } else
            return mid;
    }
    return -1;
}

// 查找第一个等于给定值的元素
int searchFirstEqual(vector<int> l, int x)
{
    int left = 0, right = l.size() - 1, mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (x < l[mid])
        {
            right = mid - 1;
        } else if (x > l[mid])
        {
            left = mid + 1;
        } else
        {
            if (mid - 1 < 0 || l[mid - 1] != l[mid])
            {
                return mid;
            }
            right = mid - 1;
        }
    }
    return -1;
}

int searchLastEqual(vector<int> v, int x)
{
    int l = 0, r = v.size() - 1, m, t = -1;
    while (l <= r)
    {
        m = (l + r) / 2;
        if (v[m] == x)
        {
            t = m;
            l = m + 1;
        } else if (v[m] < x)
        {
            l = m + 1;
        } else
        {
            r = m - 1;
        }
    }
    return t;
}

// 查找第一个大于等于的,没有就返回-1
int searchFirstLargeEqual(vector<int> v, int x)
{
    int l = 0, r = v.size() - 1, m, t = -1;
    while (l <= r)
    {
        m = (l + r) / 2;
        if (v[m] >= x)
        {
            t = m;
            r = m - 1;
        } else
        {
            l = m + 1;
        }
    }
    return t;
}

int main()
{
    //                0   1  2  3  4  5  6  7  8  9  10 11 12
    vector<int> l = {-11, 0, 0, 1, 1, 1, 2, 2, 3, 5, 7, 9, 10};
//    vector<int> l ={1};
//    cout << searchEqual(l, 0) << endl;
//    cout << searchFirstEqual(l, 0) << endl;
//    cout << searchLastEqual(l, -101) << endl;
    cout << searchFirstLargeEqual(l, -88) << endl;
    return 0;
}